// to run: ./a.out N | FILE
// N: number of items
// FILE: file name that contains number of items and items infor

// If only N is specified then we run with a randomized input but don't store the input
// If N and FILE are specified then we run with a randomized input and store the input in to FILE
// If only FILE is specified then we run with input from FILE

// to compile: g++ -I/opt/local/include -L/opt/local/lib -lboost_program_options bin-packing.cpp

#include <set>
#include <vector>
#include <fstream>
#include <iostream>

#include <boost/program_options.hpp>

#define NO_ITEMS "n"
#define FILE     "file"
#define MODE     "mode"


typedef std::vector<int> Items;
typedef std::vector<int> VBins;
typedef std::multiset<int> SBins;


void
read_input(std::size_t& n, const std::string& filename, Items& items)
{
  if (n == 0) // read input from file
    {
      std::ifstream file(filename.c_str());
      if (file.is_open())
	{
	  file >> n;
	  int val;
	  for (std::size_t i = 0; i < n; ++i)
	    {
	      file >> val;
	      items.push_back(val);
	    }
	  file.close();
	}
      else
	{
	  std::cerr << "Failed to open " << filename << "!" << std::endl;
	  exit(1);
	}
    }
  else // generate input of n items and store into FILE
    {
      srand( time(NULL) );
      std::ofstream file(filename.c_str());
      int val;

      file << n << std::endl;
      for (std::size_t i = 0; i < n; ++i)
	{
	  val = rand() % 100;
	  file << val << std::endl;
	  items.push_back(val);
	}

      file.close();
    }
}



std::size_t
best_fit_nlogn(Items& items, SBins& sbins)
{
  //std::cerr << "In nlogn" << std::endl;
  for (Items::const_iterator it = items.begin(); it != items.end(); ++it)
    {
      int weight = *it;
      SBins::iterator bt = sbins.upper_bound(weight);

      //std::cerr << "Processing weight = " << weight << std::endl;

      if (bt == sbins.end())
	{
	  // a small trick here, since upper_bound aims for strict greaterness,
	  // we need 101 to allow bins full of 100 units
	  sbins.insert(101 - weight);
	  //std::cerr << "Pick a new bin. size = " << sbins.size() << std::endl;
	}
      else
	{
	  int extra = *bt;
	  extra -= weight;
	  sbins.erase(bt);
	  sbins.insert(extra);

	  //std::cerr << "Put to bin [" << extra+weight << "] " << extra << ". size = " << sbins.size() << std::endl;
	}
    }

  return sbins.size();
}



std::size_t
best_fit_n2(Items& items, VBins& vbins)
{
  //std::cerr << "In n^2" << std::endl;  
  for (Items::const_iterator it = items.begin(); it != items.end(); ++it)
    {
      int weight = *it;
      VBins::iterator bt;
      int min = 100;

      //std::cerr << "Processing weight = " << weight << std::endl;

      for (VBins::iterator jt = vbins.begin(); jt != vbins.end(); ++jt)
	{
	  int extra = *jt - weight;
	  if ((extra >= 0) && (extra < min))
	    {
	      min = extra;
	      bt = jt;
	    }
	}

      if (min == 100)
	{
	  vbins.push_back(100 - weight);
	  //std::cerr << "Pick a new bin. size = " << vbins.size() << std::endl;
	}
      else
	{
	  //std::cerr << "Put to bin [" << min+weight << "] " << min << ". size = " << vbins.size() << std::endl;
	  *bt = min;
	}
    }

  return vbins.size();
}



int
main(int argc, char* argv[])
{
  boost::program_options::options_description desc("Command line arguments");

  std::size_t n;
  std::string filename;
  std::size_t mode; // 0: run O(n^2) algorithm
                    // 1: run O(nlogn) algorithm
                    // 2: run both algorithms and compare the running time

  desc.add_options()
    (NO_ITEMS, boost::program_options::value<std::size_t>(&n)->default_value(0), "number of items")
    (FILE, boost::program_options::value<std::string>(&filename)->default_value("bin-packing.inp"), "file storing input")
    (MODE, boost::program_options::value<std::size_t>(&mode)->default_value(1), "choose mode")
    ;

  boost::program_options::variables_map vm;        
  boost::program_options::store(boost::program_options::parse_command_line(argc, argv, desc), vm);
  boost::program_options::notify(vm);   

  Items items;
  SBins sbins;
  VBins vbins;

  read_input(n, filename, items);

  std::cout << "[nlogn] No bins = " << best_fit_nlogn(items, sbins) << std::endl;
  std::cout << "[n^2]   No bins = " << best_fit_n2(items, vbins) << std::endl;   
}

// Local Variables:
// mode: C++
// End:
